package leetcode_141_160;

public class findMin_153 {
    /**
     *寻找旋转排序数组(不包含重复元素)中的最小值
     * 算法时间复杂度必须为 O(log n)
     */
    public int findMin(int[] nums) {
        /**
         * 最先想到的思路
         * 经过旋转，数组可以看作是两个有序数组的拼接，只需要找出左边数组的起点即可
         * 但是不满足时间复杂度
         * 0ms
         */
        int left=0,right=nums.length-1;
        if(nums.length==1 || nums[left]<nums[right])  //如果此时整个数组有序，头元素一定小于尾元素
            return nums[left];
        while (left<=right){
            if(nums[left+1]<nums[left])
                return nums[left+1];
            if(nums[right-1]>nums[right])
                return nums[right];
            left++;
            right--;
        }
        return 0;
    }


    /**
     * 二分法思路与我很像，都是找出右边数组的起点
     * 但是思路更简单，实时判断左右哪部分是有序数组
     * @param nums
     * @return
     */
    public int findMin2(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        if(nums[r] >= nums[l]) return nums[0];
        while(l <= r) {
            int mid = (r - l) / 2 + l;
            if(nums[mid] >= nums[0]) {    //中值大于左边界，说明左半部分是前一个有序数组的一部分，去右半部分找
                l = mid + 1;
            } else {                  //中值小于左边界，说明右半部分是后一个有序数组的一部分，去左半部分找
                r = mid - 1;
            }
        }
        return nums[l];
    }


    /**
     * 154题，区别是可能含有重复元素
     */
    public int findMin3(int[] nums) {
        /**
         * 二分法显然失效了，因为重复元素，没办法实时判断哪边是有序的
         * 采用我的老办法
         * 0ms
         */
        int left=0,right=nums.length-1;
        if(nums.length==1 || nums[left]<nums[right])  //如果此时整个数组有序，头元素一定小于尾元素
            return nums[left];
        while (left<=right){
            if(nums[left+1]<nums[left])
                return nums[left+1];
            if(nums[right-1]>nums[right])
                return nums[right];
            left++;
            right--;
        }
        return nums[0];
    }
}
